package niuke.week01;

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

/**
 开始时你的能力是0，你的目标是从0号怪兽开始，通过所有的怪兽。
     如果你当前的能力，小于i号怪兽的能力，你必须付出money[i]的钱，贿赂这个怪兽，然后怪兽就会加入你，他的能力直接累加到你的能力上；
     如果你当前的能力，大于等于i号怪兽的能力，你可以选择直接通过，你的能力并不会下降，你也可以选择贿赂这个怪兽，然后怪兽就会加入你，他的能力直接累加到你的能力上。
 返回通过所有的怪兽，需要花的最小钱数。


 */
public class HitBeast {
    public static void main(String[] args) {
        System.out.println(solution2());
    }


    public static int solution2() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Integer [] moneyArray = new Integer[n];
        Integer [] abilityArray = new Integer[n];

        int maxMoney = 0;
        for (int i=0;i<n;i++){
            abilityArray[i] = sc.nextInt();
            moneyArray[i] = sc.nextInt();
            maxMoney+=moneyArray[i];
        }

//        dp[i][j] : 通关到第i个怪兽(下标从0开始)，花j钱，达到的最大能力
        Integer [][]dp = new Integer[n][maxMoney+1];

        for (int i =0;i<n;i++)  //初始化
            for (int j =0;j<=maxMoney;j++)
                dp[i][j] = -1;

       //第一行初始化
        dp[0][moneyArray[0]] = abilityArray[0];
        for (int i=1;i<n;i++){
            for (int j = 1;j<=maxMoney;j++){
                //收买
                if(j - moneyArray[i]>=0 && dp[i - 1][j - moneyArray[i]]!=-1){
                    dp[i][j] = dp[i - 1][j - moneyArray[i]] + abilityArray[i];
                }

                //不买
                if(dp[i-1][j]>=abilityArray[i]){
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i][j])  ;

                }
            }
        }

//        for (int i =0;i<n;i++) {
//            for (int j = 0; j <= maxMoney; j++){
//                System.out.print(dp[i][j] + ",");
//            }
//            System.out.println();
//        }

        int res =0;
        for (int i=0;i<=maxMoney;i++){
            if (dp[n-1][i]!=-1){
                res =i;
                    break;
            }
        }
        return  res;
    }




    public static int solution1() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Integer [] moneyArray = new Integer[n];
        Integer [] abilityArray = new Integer[n];

        int maxAbility = 0;
        for (int i=0;i<n;i++){
            abilityArray[i] = sc.nextInt();
            maxAbility+=abilityArray[i];
            moneyArray[i] = sc.nextInt();
        }

//        dp[i][j] : 通关到第i个怪兽(下标从0开始)，能力达到j，至少多钱
        Integer [][]dp = new Integer[n][maxAbility+1];

        for (int i =0;i<n;i++)  //初始化
            for (int j =0;j<=maxAbility;j++)
                dp[i][j] = -1;

//第一行初始化
        dp[0][abilityArray[0]] = moneyArray[0];


        for (int i=1;i<n;i++){
            for (int j = 1;j<=maxAbility;j++){
                if(j<abilityArray[i]) {  //能力不够，就不用考虑是否收买了
                    dp[i][j] = -1;
                    continue;
                }

                int  buy = Integer.MAX_VALUE;
                int  nobuy = Integer.MAX_VALUE;


                boolean buyCondition = j-abilityArray[i]>=0 && dp[i-1][j-abilityArray[i]]!=-1;

                boolean noBuyCondition = dp[i-1][j]!=-1;

                //                  选择收买所花的钱
                if(buyCondition)
                  buy = dp[i-1][j-abilityArray[i]]+moneyArray[i];


                if(noBuyCondition)      //不收买所花的钱
                  nobuy = dp[i - 1][j];


                if( buyCondition || noBuyCondition)
                    dp[i][j] = Math.min(buy,nobuy);

            }
        }

        for (int i =0;i<n;i++) {  //初始化
            for (int j = 0; j <= maxAbility; j++){
                System.out.print(dp[i][j] + ",");
            }
            System.out.println();
        }

        int res = Integer.MAX_VALUE;
        for (int i=0;i<=maxAbility;i++){
            if (dp[n-1][i]<res && dp[n-1][i]!=-1)
                res =dp[n-1][i];
        }
       return  res;
    }

}